package leetcode_301_400;

import java.util.*;

public class LeeCode_395 {
    public static void main(String[] args) {
        System.out.println(longestSubstring("aaabb", 3));
        System.out.println(longestSubstring("ababbc", 2));
        System.out.println(longestSubstring("bbaaacbd", 3));
    }

    private static int longestSubstring(String s, int k) {
        int n = s.length();
        int[][] map = new int[26][n];
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (i == 0) {
                map[c - 'a'][i] = 1;
            } else {
                for (int j = 0; j < 26; j++) {
                    map[j][i] = map[j][i - 1];
                }
                map[c - 'a'][i] = map[c - 'a'][i - 1] + 1;
            }
        }
        int[] ans = new int[1];
        f(s, map, 0, n - 1, ans, k);
        return ans[0];
    }

    private static void f(String s, int[][] map, int l, int r, int[] ans, int k) {
        if (r - l + 1 <= ans[0])
            return;
        Set<Character> set = new HashSet<>();
        List<Integer> list = new ArrayList<>();
        for (int i = l; i <= r; i++) {
            char c = s.charAt(i);
            if (set.contains(c)){
                list.add(i);
                continue;
            }
            int count = l == 0 ? map[c - 'a'][r] : map[c - 'a'][r] - map[c - 'a'][l - 1];
            if (count < k) {
                list.add(i);
                set.add(c);
            }
        }
        if (list.size() == 0) {
            ans[0] = Math.max(ans[0], r - l + 1);
        } else {
            int pre = -1;
            for (Integer mid : list) {
                f(s, map, pre + 1, mid - 1, ans, k);
                pre = mid;
            }
            f(s, map, pre + 1, r, ans, k);
        }
    }
}
